package 牛客.链表;

import 剑指offer.ListNode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class BM12单链表的排序 {

    public ListNode sortInList (ListNode head) {
        // write code here
        // 对链表进行 归并排序.分治法
        if (head==null || head.next==null) {
            return head;
        }
        //快慢指针找到中点位置，把链表一分为二
        //slow最后指向：奇数个找到中点，偶数个找到中心左边
        ListNode slow=head;
        ListNode fast=head.next;
        while (fast!=null && fast.next!=null) {
            slow=slow.next;
            fast=fast.next.next;
        }

        ListNode tmp=slow.next;
        slow.next=null;
        ListNode left=sortInList(head);
        ListNode right=sortInList(tmp);

        //合并两个有序链表
        ListNode curHead=merge(left,right);

        return curHead;
    }

    private ListNode merge(ListNode left, ListNode right) {
        if (left==null) {
            return right;
        }
        if (right==null) {
            return left;
        }

        ListNode dummyNode=new ListNode(-1);
        ListNode cur=dummyNode;
        while (left!=null && right!=null) {
            if (left.val<right.val) {
                cur.next=left;
                left=left.next;
            }else {
                cur.next=right;
                right=right.next;
            }
            cur=cur.next;
        }
        cur.next= left==null ? right : left;
        return dummyNode.next;
    }

    private ListNode merge2(ListNode left, ListNode right) {
        if (left==null) {
            return right;
        }else if (right==null) {
            return left;
        }else if (left.val<right.val) {
            left.next=merge2(left.next,right);
            return left;
        }else {
            right.next=merge2(left,right.next);
            return right;
        }
    }


    public ListNode sortInList1 (ListNode head) {
        // write code here
        // 转化为数组排序
        if(head==null || head.next==null) {
            return head;
        }
        List<Integer> list=new ArrayList<>();
        ListNode cur=head;
        while (cur!=null) {
            list.add(cur.val);
            cur=cur.next;
        }
        Collections.sort(list);

        cur=head;
        for (int i = 0; i < list.size(); i++) {
            cur.val=list.get(i);
            cur=cur.next;
        }
        return head;

//        ListNode dummyNode=new ListNode(-1);
//        cur=dummyNode;
//        for (int i = 0; i <list.size(); i++) {
//            cur.next=new ListNode(list.get(i));
//            cur=cur.next;
//        }
//        return dummyNode.next;
    }
}
